package algorithmic_data_structure.马拉车算法;

import utils.PrintUtil;
import org.junit.Test;

public class 手写马拉车 {
    public static int manacher(String s){
        if (s == null || s.length() == 0){
            return 0;
        }
        char[] str = getLongArray(s);
        //记录每个位置的回文半径
        int[] rArr = new int[str.length];
        int C = -1;
        int R = -1; //R 位置 记录的是刚好不是回文串的地方
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < str.length; i++) {
            rArr[i] = R > i ? Math.min(R - i,rArr[C - (i - C)]) : 1;
            while (i - rArr[i] >= 0 && i + rArr[i] < str.length){
                if (str[i - rArr[i]] == str[i + rArr[i]]){
                    rArr[i] ++;
                }else{
                    break;
                }
            }
            if (i + rArr[i] > R){
                R = i + rArr[i];
                C = i;
            }
            max = Math.max(max,rArr[i] * 2 - 1);
        }
        return max/2;
    }

    private static char[] getLongArray(String s) {
        char[] res = new char[s.length()*2 + 1];
        res[0] = '#';
        int index = 0;
        for (int i = 1; i < res.length; i+=2) {
            res[i] = s.charAt(index++);
            res[i+1] = '#';
        }
        return res;
    }
    @Test
    public void test(){
        PrintUtil.printArray(getLongArray("lwl"));
    }

}
